import java.util.ArrayList;
import java.util.List;

/**
 * @author shuang
 * @date 2022/5/2 0:12
 * [312. 戳气球](https://leetcode-cn.com/problems/burst-balloons/)
 * https://leetcode-cn.com/problems/burst-balloons/
 */
public class Solutions_312 {
    public static void main(String[] args) {
        int[] nums1 = {3, 1, 5, 8};  // output: 167
//        解释：nums = {3, 1, 5, 8} --> {3, 5, 8} --> {3, 8} --> {8} --> {}
//        coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

        int[] nums2 = {1, 5};  // output: 10

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);

        Solutions_312 obj = new Solutions_312();
        for (int[] input : inputs) {
            int result = obj.maxCoins(input);
            System.out.println(result);
        }
    }

    /**
     * 动态规划，自顶向上
     * @param nums
     * @return
     */
    private int maxCoins(int[] nums) {
        int len = nums.length;
        // 构造虚拟数组，防索引越界
        int[] newArr = new int[len + 2];
        // 虚拟数组的首位和末位都设置为 1
        newArr[0] = newArr[newArr.length - 1] = 1;
        // 将 nums 中的元素填充到虚拟数组中
        System.arraycopy(nums, 0, newArr, 1, nums.length);

        // 动态规划数组 dp[0, 4] = 167：表示在数组 nums 中，索引 [0, 4) 的区间内，能够获取到的最大分值为 167
        int[][] dp = new int[len + 2][len + 2];
        // 自底向上的方式填充动态规划数组
        // 左边界
        for (int i = len - 1; i >= 0; i--) {
            // 右边界
            for (int j = i + 2; j <= len + 1; j++) {
                // 中间取值，取值范围为 (i, j) 之中
                for (int k = i + 1; k < j; k++) {
                    // k 与相邻索引 i、j 上元素的乘积
                    int sum = newArr[i] * newArr[j] * newArr[k];
                    // 若本次取 k 索引，则需要加上左边界[i, k) 的最优分值 + 右边界 [k, j) 的最优分值
                    sum += dp[i][k] + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], sum);
                }
            }
        }
        return dp[0][len + 1];
    }
}

